package mo.daliy;

import java.util.*;

public class L3123 {

    public boolean[] findAnswer(int n, int[][] edges) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            int w = edges[i][2];
            graph[x].add(new int[]{y, w});
            graph[y].add(new int[]{x, w});
        }
        int[] starts = new int[n];
        Arrays.fill(starts, Integer.MAX_VALUE / 3);
        int[] ends = new int[n];
        Arrays.fill(ends, Integer.MAX_VALUE / 3);

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p[1]));
        priorityQueue.add(new int[]{0, 0});
        while (!priorityQueue.isEmpty()) {
            int[] cur = priorityQueue.poll();
            if (starts[cur[0]] != Integer.MAX_VALUE / 3) {
                continue;
            }
            starts[cur[0]] = cur[1];
            List<int[]> nexts = graph[cur[0]];
            for (int[] next : nexts) {
                if (starts[next[0]] != Integer.MAX_VALUE / 3) {
                    continue;
                }
                priorityQueue.add(new int[]{next[0], cur[1]+next[1]});
            }
        }

        priorityQueue.add(new int[]{n-1, 0});
        while (!priorityQueue.isEmpty()) {
            int[] cur = priorityQueue.poll();
            if (ends[cur[0]] != Integer.MAX_VALUE / 3) {
                continue;
            }
            ends[cur[0]] = cur[1];
            List<int[]> nexts = graph[cur[0]];
            for (int[] next : nexts) {
                if (ends[next[0]] != Integer.MAX_VALUE / 3) {
                    continue;
                }
                priorityQueue.add(new int[]{next[0], cur[1]+next[1]});
            }
        }

        boolean[] res = new boolean[edges.length];
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int x = edge[0];
            int y = edge[1];
            int w = edge[2];
            if (starts[x] + ends[y] + w == ends[0] || starts[y] + ends[x] + w == ends[0]) {
                res[i] = true;
            }
        }

        return res;
    }

}
